The subject matter disclosed herein relates to an aircraft motion planning method and, more particularly, to an aircraft motion planning method using a recursive rapidly exploring random tree (RRT) algorithm with a goal-rooted planning tree for cost-to-go computation.
Motion planning or path planning algorithms solve a problem of navigation an aircraft from point A to point B while dealing with motion constraints, mission constraints and any other time-based or vehicle-based constraints. When the planning problem is implemented on a real-time or online framework, the planner has to repeatedly solve the problem starting from A as the vehicle agent gathers relevant new information that may have been previously unknown regarding the operating space, constraints and vehicle dynamics. This “repeated” solution terminates when the vehicle eventually reaches point B (in a multipoint problem, this continues onto point C and beyond).
A problem often faced by recursive planners relates to a need to maintain an ability to react to local changes while keeping global objectives intact. As an example, a planner needs to be able to insure that an aircraft avoids obstacles while the distance to a destination is continually reduced to the extent possible.
A motion planning problem for autonomous vehicles may be solved by various means (model-predictive optimal control, sampling-based planning, potential-field based planners, grid based planners (A*/D*)). Each approach has a trick to bring in the notion for cost-to-go in the respective framework. Typically this tends to be a “straight line distance” to goal from the end of local planning horizon, or some other conservative approach. The reason for this conservative approach is that these techniques tend to be computationally expensive so providing a more realistic estimate of cost-to-go involves solving a global problem repeatedly, which is computationally prohibitive or may be impossible in a given time.